from algorithm import *
import operator

def majorityCnt(classList):
    classCount={}
    for vote in classList:
        if vote not in classCount.keys(): classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(
        classCount.itemItems(),
        key=operator.itemgetter(1),
        reverse=True
    )
    return sortedClassCount

'''
    #生成决策树,方法：
    先找到最佳分类类别, bestFeat，然后遍历它的每个值，
'''
def createTree(dataSet, labels):

    #最后一列：判定结果列表
    classList = [example[-1] for example in dataSet]

    #若第一个元素的个数就是整个列表的行数，则只有一个类别，直接返回
    if classList.count(classList[0]) == len(classList):
        return classList[0]

    #如果只剩下最后一个特征，则直接返回
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)

    #查找最匹配的项目
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel =labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    #删除
    del(labels[bestFeat])
    #
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(
            splitDataSet(dataSet, bestFeat, value),
            subLabels
        )
    return myTree

def test():
    myDat, labels = createDataSet()
    myTree = createTree(myDat, labels)
    print(myTree)

test()